/*
 * 18. Write a program that reads from the console a
 * rectangular matrix of integers and finds in
 * it the larges set of adjacent equal cells. 
 */

// Използваният алгоритъм е depth first search, повече информация тук:
// http://www.kirupa.com/developer/actionscript/depth_breadth_search4.htm

package _3;

import java.util.BitSet;
import java.util.Scanner;
import java.util.Stack;
import java.util.Vector;

public class _18 {
	public static int input (String question, Scanner scn) {
		System.out.print (question);

		if (!scn.hasNextInt ()) {
			System.err.println ("error:mismatched input");
			System.exit (1);
		}

		return scn.nextInt ();
	}

	public static void main (String[] args) {
		// Ако userInput е false, то се използва матрицата, зададена в
		// условието. В противен случай потребителят въвежда размерите и
		// стойностите ѝ.
		boolean userInput = true;

		// Матрицата, която съхранява всички върхове на графа.
		int[][] matrix = { { 1, 2, 3, 2, 3, 1, 2 }, { 1, 2, 2, 2, 2, 5, 2 },
				{ 2, 3, 4, 3, 2, 1, 2 }, { 1, 2, 2, 2, 2, 2, 1 } };

		if (userInput) {
			Scanner scn = new Scanner (System.in);

			int m = input ("m ?= ", scn);
			int n = input ("n ?= ", scn);
			matrix = new int[m][n];

			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					matrix[i][j] = input ("matrix[" + i + "][" + j + "] ?= ",
							scn);
				}
			}
		}

		// Стек, в който се пазят върховете за бъдещ обход.
		Stack<_18_Vertex> open = new Stack<_18_Vertex> ();

		// Битови маски, които съдържат true, ако даден връх е обходен, и false,
		// ако все още не е.
		BitSet[] checked = new BitSet[matrix.length];

		// Инициализира масива от BitSet обекти checked.
		for (int i = 0; i < matrix.length; i++) {
			checked[i] = new BitSet (matrix[0].length);
		}

		// Порменлива, в която се записва най–големият брой съседни елементи с
		// еднакви стойности.
		int mostMatches = Integer.MIN_VALUE;

		// Променлива, в която се записва стойността на тия елементи.
		int mostMatchedValue = 0;

		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				if (!checked[i].get (j)) {
					if (!open.empty ()) {
						open.clear ();
					}

					open.add (new _18_Vertex (i, j, matrix[i][j]));
					checked[i].set (j, true);

					int matches;
					for (matches = 0; open.size () > 0; matches++) {
						_18_Vertex current = open.pop ();

						for (_18_Vertex neighbor : neighborsByValue (current,
								matrix)) {
							if (!checked[neighbor.row].get (neighbor.col)) {
								open.add (neighbor);
								checked[neighbor.row].set (neighbor.col, true);
							}
						}
					}

					if (matches > mostMatches) {
						mostMatches = matches;
						mostMatchedValue = matrix[i][j];
					}
				}
			}
		}

		System.out.println ("Most matches: " + mostMatches);
		System.out.println ("Most matched value: " + mostMatchedValue);
	}

	public static _18_Vertex[] neighbors (_18_Vertex vertex, int[][] matrix) {
		Vector<_18_Vertex> v = new Vector<_18_Vertex> (4);
		int tmp;

		// Проверява за съседен връх по левия хоризонтал.
		if (vertex.col - 1 >= 0) {
			tmp = vertex.col - 1;
			v.add (new _18_Vertex (vertex.row, tmp, matrix[vertex.row][tmp]));
		}

		// Проверява за съседен връх по десния хоризонтал.
		if (vertex.col + 1 < matrix[0].length) {
			tmp = vertex.col + 1;
			v.add (new _18_Vertex (vertex.row, tmp, matrix[vertex.row][tmp]));
		}

		// Проверява за съседен връх по горния вертикал.
		if (vertex.row - 1 >= 0) {
			tmp = vertex.row - 1;
			v.add (new _18_Vertex (tmp, vertex.col, matrix[tmp][vertex.col]));
		}

		// Проверява за съседен връх по горния вертикал.
		if (vertex.row + 1 < matrix.length) {
			tmp = vertex.row + 1;
			v.add (new _18_Vertex (tmp, vertex.col, matrix[tmp][vertex.col]));
		}

		/*
		 * // Принтира откритите съседини върхове. System.out.println
		 * ("Neighbors are:"); for (_17_Vertex e : v) { e.print (); }
		 * System.out.println ();
		 */

		_18_Vertex[] a = new _18_Vertex[v.size ()];
		return v.toArray (a);
	}

	public static _18_Vertex[] neighborsByValue (_18_Vertex vertex,
			int[][] matrix) {
		Vector<_18_Vertex> v = new Vector<_18_Vertex> (4);

		/*
		 * Тези редове + функцията e.print () по–долу принтират откритите
		 * съседни върхове с еднакви стойности. System.out.print
		 * ("Neighbors by value of "); vertex.print ();
		 */

		for (_18_Vertex e : neighbors (vertex, matrix)) {
			if (e.value == vertex.value) {
				v.add (e);
				// e.print ();
			}
		}

		_18_Vertex[] a = new _18_Vertex[v.size ()];
		return v.toArray (a);
	}
}
